#include<stdlib.h>
#include<stdio.h>

#define vertex 5    // 顶点的个数
// 无向图的邻接表实现

typedef struct ArcNode
{
    int adjvex;   //存放该边指向的位置
    struct ArcNode* nextArcNode;  //指向下一条边的指针
}ArcNode;


typedef struct 
{
    char data;   // 存放顶点的信息
    ArcNode* firstNode;   //指向第一条边的指针，单链表的第一个结点
}VNode;

// 整个图的定义
typedef struct 
{
    VNode vertices[vertex];    // 每个的顶点的数组
    int versNum,arcsNum;     //顶点数和边数
}AMGraph;

typedef struct 
{
    int* base;  //动态分配的内存空间
    int tail;   // 尾指针
}SqQueue;

// 寻找数据所在结点的位置
int Location(AMGraph* graph,char c)
{
    int index;
    for(int i=0;i<graph->versNum;i++)
    {
        if(graph->vertices[i].data==c)
        {
            index=i;
            break;
        }
    }
    return index;
}

// 结点的插入,头插法
void insertNode(AMGraph* graph,ArcNode* node,int index)
{
    if(graph->vertices[index].firstNode==NULL)
    {
        graph->vertices[index].firstNode=node;
        node->nextArcNode=NULL;
    }
    else
    {
        node->nextArcNode=graph->vertices[index].firstNode;
        graph->vertices[index].firstNode=node;   
    }
}

// 建立以邻接表为存储结构的图
void creatUMN(AMGraph* graph)
{
    char buff[10];
    int count=0;  // 记录文件总行数
    FILE* f=fopen("./ax1.txt","r");
    while(fgets(buff,10,f)!=NULL)
    {
        count++;
    }
    fseek(f,0,SEEK_SET);   // 修改文件指针偏移

    graph->versNum=vertex;  //顶点的个数
    graph->arcsNum=count-vertex;  // 边的个数

    for(int i=0;i<vertex;i++)    // 初始化顶点信息
    {
        fgets(buff,10,f);
        graph->vertices[i].data=buff[0];
        graph->vertices[i].firstNode=NULL;
    }
    int v1,v2;   // 临时记录两个顶点的位置信息
    for(int i=0;i<graph->arcsNum;i++)
    {
        fgets(buff,10,f);
        v1=Location(graph,buff[0]);
        v2=Location(graph,buff[2]);      // 找到边的两个结点的位置

        ArcNode* p1=(ArcNode*) malloc(sizeof(ArcNode));
        p1->adjvex=v2;      // 赋值边的结点信息
        insertNode(graph,p1,v1);    // 结点插入

        ArcNode* p2=(ArcNode*) malloc(sizeof(ArcNode));
        p2->adjvex=v1;
        insertNode(graph,p2,v2);        
    }
}

// 深度优先遍历，基于图的邻接表,递归实现
void deepSearch(AMGraph* graph,int* visited,int index)
{
    printf("%c\t",graph->vertices[index].data);
    visited[index]=1;
    ArcNode* tempNode=graph->vertices[index].firstNode;
    while(tempNode!=NULL)
    {
        if(visited[tempNode->adjvex]!=1)
        {
            deepSearch(graph,visited,tempNode->adjvex);
        }
        tempNode=tempNode->nextArcNode;
    }
}

// 队列的实现-->用于广度优先遍历

// 队列的初始化
SqQueue initQueue()
{
    int* basex=(int*) malloc(10*sizeof(int));
    SqQueue queue;
    queue.base=basex;
    for(int i=0;i<10;i++)
    {
        queue.base[i]=-1;
    }
    queue.tail=0;
    return queue;
}

// 队列的出队
int OutQueue(SqQueue* queue)
{
    int temp=-1;
    if(queue->base[0]!=-1)
    {
        temp=queue->base[0];
        for(int i=0;i<queue->tail-1;i++)
        {
            queue->base[i]=queue->base[i+1];
        }
        queue->tail--;
        queue->base[queue->tail]=-1;
    }
    return temp;
}

// 队列的入队
void joinQueue(SqQueue* queue,int data)
{
    queue->base[queue->tail++]=data;
}

//判断队列是否为空
int emptyQueue(SqQueue* queue)
{
    if(queue->tail==0)
    {
        return 1;
    }
    else
        return 0;
}

// 广度优先遍历
void spanSearch(AMGraph* graph,int index)
{
    SqQueue queue=initQueue();

    int visited[vertex]={0};
    joinQueue(&queue,index);
    visited[index]=1;
    while(!emptyQueue(&queue))
    {
        ArcNode* tempNode=graph->vertices[index].firstNode;
        index=OutQueue(&queue);
        printf("%c\t",graph->vertices[index].data);
        while (tempNode!=NULL)
        {
            if(visited[tempNode->adjvex]!=1)
            {
                visited[tempNode->adjvex]=1;
                joinQueue(&queue,tempNode->adjvex);
            }
            tempNode=tempNode->nextArcNode;
        }
        
    }

}

//计算无向图邻接矩阵表示法中边的度
int countTuDegree(AMGraph* graph,int index)
{
    int sum=0;
    ArcNode* node=graph->vertices[index].firstNode;
    while (node!=NULL)
    {
        sum++;
        node=node->nextArcNode;
    }
    return sum;
}

void main()
{
    AMGraph graph;
    creatUMN(&graph);
    int Visted[vertex]={0};
    deepSearch(&graph,Visted,1);
    printf("\n");
    spanSearch(&graph,1);

    printf("\n顶点为a的边的度%d\n",countTuDegree(&graph,0));
    printf("顶点为b的边的度%d\n",countTuDegree(&graph,1));
}